#include "seq-list.cpp"

/***
 * 希尔排序
 * 基本思路: 按照不同步长对元素进行插入排序
 * 时间复杂度: 平均 O(n^1.3) 最优O(n) 最坏O(n^2)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 * */

void sort(SqList &L)
{
    int i, j, inc, key;
    // 初始增量 n/2 每一趟后除以二
    for (int inc = L.length / 2; inc > 0; inc /= 2)
    {
        // 每一趟采用插入排序
        for (i = inc; i < L.length; i++)
        {
            key = L.data[i];
            for (j = i; j >= inc && key < L.data[j - inc]; j -= inc)
                L.data[j] = L.data[j - inc];
            L.data[j] = key;
        }
        // 输出过程
        printList(L);
    }
}

int main(int argc, char const *argv[])
{
    SqList L;
    int data[10] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    L.data = data;
    L.length = 10;
    printList(L);
    sort(L);
    printList(L);
    return 0;
}
